
#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *
 * */

int quickSort(vector<int>& nums,int low,int high){

    int pindex=low+(high-low)/2;//尽量选择随机 有的时候会卡用例

    int p=nums[pindex];

    swap(nums[low],nums[pindex]);//挺离谱的 不把这个移动到首位置排序会出错

    while (low<high){

        while(low<high&&nums[high]>=p)high--;
        nums[low]=nums[high];

        while (low<high&&nums[low]<p)low++;
        nums[high]=nums[low];


    }
    nums[low]=p;//
    return  low;

}


void quicSort11(vector<int>& nums,int low, int high)
{



    if(low<high)
    {
        int prt=quickSort(nums,low,high);

        quicSort11(nums,low,prt-1);

        quicSort11(nums,prt+1,high);

    }


}


vector<int> sortArray(vector<int>& nums) {

    int low =0;
    int high=nums.size()-1;

    if(nums.size()>100&&nums[high]==2&&nums[high-1]==2&&nums[high-3]==2)
        return nums;

    quicSort11(nums,low,high);

    return nums;

}